import java.util.*;

/**
 * @Author ZhangCuirong
 * @Date 2025/9/4 9:03
 * @description:
 */
public class Solution773 {
    // 记录一维字符串的相邻索引
    int[][] neighbor = new int[][]{
            {1, 3},
            {0, 4, 2},
            {1, 5},
            {0, 4},
            {3, 1, 5},
            {4, 2}
    };

    public int slidingPuzzle(int[][] board) {
        StringBuilder convertString = new StringBuilder();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                convertString.append(board[i][j]);
            }
        }
        String finalString = "123450";
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        queue.add(convertString.toString());
        visited.add(convertString.toString());
        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String node = queue.poll();
                if (node.equals(finalString)) {
                    return step;
                }
                int index = 0;
                while (node.charAt(index) != '0') {
                    index++;
                }
                for (int next : neighbor[index]) {
                    String nextString = swap(node, index, next);
                    if (!visited.contains(nextString)) {
                        queue.add(nextString);
                        visited.add(nextString);
                    }
                }
            }
            step++;
        }
        return -1;
    }

    public String swap(String s, int i, int j) {
        char[] charArray = s.toCharArray();
        char temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
        return new String(charArray);
    }

    public static void main(String[] args) {
        Solution773 solution = new Solution773();
        System.out.println(solution.slidingPuzzle(new int[][]{{1, 2, 3}, {4, 0, 5}}));
        System.out.println(solution.slidingPuzzle(new int[][]{{1, 2, 3}, {5, 0, 4}}));
        System.out.println(solution.slidingPuzzle(new int[][]{{4, 1, 2}, {5, 0, 3}}));
    }
}
